package leetcode.N1_N100;

import leetcode.comm.ListNode;

public class N2 {

    public static void main(String[] args) {
        ListNode l1 = ListNode.generate(8,9,9);
        ListNode l2 = ListNode.generate(2);
        System.out.println(addTwoNumbersV1(l1, l2));
        ListNode l11 = ListNode.generate(8,9,9);
        ListNode l22 = ListNode.generate(2);
        System.out.println(addTwoNumbersV2(l11, l22));

    }

    // ------------------------- 解法一 -----------------------

    // 1.创建一个新链表用于存放结果
    // 2.从个位开始相加，逢十进位，用carry标识
    // 3.当任意一个数消耗完以后，进入拼接流程
    static ListNode addTwoNumbersV1(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(0);
        ListNode index = head;
        int carry = 0;

        while (l1 != null && l2 != null) {
            int val = l1.val + l2.val + carry;
            if (val >= 10) {
                carry = 1;
                val -= 10;
            } else {
                carry = 0;
            }
            index = index.next = new ListNode(val);
            l1 = l1.next;
            l2 = l2.next;
        }
        if (l1 == null) {
            doLink(index, l2, carry);
        } else {
            doLink(index, l1, carry);
        }
        return head.next;
    }

    // 拼接流程 将之前计算到的结果 和 还未算完的部分进行合并
    static void doLink(ListNode head, ListNode l, int carry) {
        if (l == null && carry == 0) {
            return;
        }
        if (l == null) {
            head.next = new ListNode(1);
            return;
        }
        head.next = l;
        if (carry == 0) {
            return;
        }
        for (ListNode node = l; node != null; node = node.next) {
            if (node.val != 9) {
                node.val = node.val + 1;
                return;
            }
            node.val = 0;
            if (node.next == null) {
                node.next = new ListNode(1);
                return;
            }
        }
    }


    // 解法二

    // 基于解法一 从逻辑将两个初始链表对其 用0补位  简化计算过程，不需要解法一中的拼接流程

    static ListNode addTwoNumbersV2(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(0);
        ListNode index = head;
        int carry = 0;
        while (l1 != null || l2 != null || carry != 0) {
            int val01 = l1 == null ? 0 : l1.val;
            int val02 = l2 == null ? 0 : l2.val;
            int val = val01 + val02 + carry;
            if (val >= 10) {
                index = index.next = new ListNode(val - 10);
                carry = 1;
            } else {
                index = index.next = new ListNode(val);
                carry = 0;
            }
            l1 = l1 == null ? l1 : l1.next;
            l2 = l2 == null ? l2 : l2.next;
        }
        return head.next;
    }


}


